package 中等.贪心思想;

/**
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 判断你是否能够到达最后一个下标。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game/
 */
public class 跳跃游戏_55 {

    public static void main(String[] args) {

        int[] nums = {3, 0, 0, 0};
        System.out.println(canJump(nums));
    }

    /**
     * 贪心思想：
     * 有元素是0才有可能到达不了终点，不然可以一步一步走到终点
     *
     * @param nums
     * @return
     */
    public static boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        //只需循环到倒数第二位
        for (int i = 0; i < nums.length - 1; i++) {
            //如果当前位置是0，则下一位才有不能到达的可能性
            if (nums[i] == 0) {
                if (!hasNext(nums, i)) {
                    return false;
                }
            }
        }
        return true;
    }

    //判断0的位置的下一位是否可以到达
    public static boolean hasNext(int[] nums, int zeroIndex) {
        int sep = 2;
        for (int i = zeroIndex - 1; i >= 0; i--) {
            if (nums[i] >= sep) {
                return true;
            }
            sep++;
        }
        return false;
    }

    /**
     * 第i的位置是否可以到达，取决于，之前的元素到达的最远距离，当前位置i+可以跳跃的距离num[i]
     *
     * @param nums
     * @return
     */
    public static boolean officialCanJump(int[] nums) {
        int maxJump = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (maxJump >= i) {
                maxJump = Math.max(maxJump, i + nums[i]);
                //如果可以到达的最远距离大于等于最后一个位置则直接返回
                if (maxJump >= nums.length - 1) {
                    return true;
                }
            } else {
                return false;
            }
        }
        return true;
    }

}
